The present invention relates to a technique for generating a practical random number sequence and its application technique.
In signature generation utilizing a public key cryptosystem, generation of a key in conducting secret communication, and a stream cipher technique, a random number sequence is highly needed. However, it is impracticable to attempt to use a truly random number sequence in these situations. In practice, there is used a pseudorandom number (hereafter simply referred to as random number) generated by a pseudorandom number generating method or an apparatus using the pseudorandom number generating method. As conditions required of the pseudorandom number as regards use in cryptograph, there are properties concerning the security, such as that the pseudorandom number is unpredictable and the initial value for determining the random number cannot be derived. In addition, in order that the pseudorandom number generating method or the pseudorandom number generating apparatus may withstand the practical use, high speed processing is demanded in software implementation or hardware implementation. In addition, the pseudorandom number generating method or the pseudorandom number generating apparatus needs to be efficient from the aspect of the implementation cost as well. For example, the number of gates required in the case of hardware implementation, and the number of steps and required memory region at the time of execution in the case of software implementation need to be small. As a general purpose cryptographic algorithm, an algorithm having no drawbacks in all of these evaluation items is desirable.
Many of currently known algorithms are suitable for either software or hardware in the aspect of performance or implementation.
For example, in the case of an algorithm especially suitable for software implementation, the circuit scale becomes large because the situation at the time of hardware implementation has not been considered.
As an example using an algorithm suitable for hardware processing, there is a pseudorandom number generating apparatus based on a linear feedback shift register (LFSR) that is small in hardware implementation scale and that is capable of realizing high speed processing as well. However, this is not sufficient in processing speed in the case where software implementation is conducted.
As such a pseudorandom number generating method that practical implementation is possible in both software and hardware, the OFB mode and the counter mode, which utilize the block cipher technique are known. However, their random number generating speed is the same as the processing speed of the block cipher. In general, the processing speed is not sufficient as compared with dedicated pseudorandom number generating apparatuses.
As the application field of the cryptographic technique spreads, there is desired a pseudorandom number generating technique that satisfies the above-described conditions in both hardware and software and that has a degree of freedom and flexibility enough to put it to practical use.
Furthermore, a pseudorandom number generating technique having high security is demanded.